ACP avec noyau

Plan

• Motivation
• Fonction noyau
• ACP avec noyau
• Application pratique
• Discussion

Motivation

• L’ACP reduit la dimention tout en conservant le maximum de variance dans les données.
• Premières composante les plus informatives.
• Information non linéaire pas facile à capturer

Exemple

Exemple

Exemple

Autre exemple

Autre exemple

Soit la transformation

\[\Phi(\textbf{x}) = (x^2, \sqrt{2}xy, y^2).\] En appliquant cette transformation sur les données originales, on obtient un problème linéaire.

Autre exemple

Autre exemple

Projection dans un autre espace d’attributs

-En général, on projète les données \(\textbf{x}\) dans un espace d’attributs par une transformation non linéaire.

-Formellement, on a

\[ \begin{aligned} \Phi: \mathbb{R}^N &\to \mathcal{F}\\ \textbf{x} &\mapsto \Phi(\textbf{x}) \end{aligned} \]

• Au lieu de faire l’apprentissage statistique sur \(\textbf{x}_1, \textbf{x}_2, \dots, \textbf{x}_N\), on le fait sur \(\Phi(\textbf{x}_1), \Phi(\textbf{x}_2), \dots, \Phi(\textbf{x}_N)\).

Transformation quadratique

Pour une données à deux attributs \(\textrm{x} = (x_1, x_2)\), on applique la transformation \(\Phi(\textbf{x}) = (x_1^2, \sqrt{2}x_1x_2, x_2^2)\). Le produit scalaire devient

\[ \begin{aligned} (\Phi(\textbf{x}_i) \cdot \Phi(\textbf{x}_j)) &= (x_{i, 1}^2 + \sqrt{2} x_{i, 1} x_{i, 2} + x_{i, 2}^2)(x_{j, 1}^2 + \sqrt{2} x_{j, 1} x_{j, 2} + x_{j, 2}^2)^T\\ &= ((x_{i, 1}x_{i, 2})(x_{j, 1}x_{j, 2})^T)^2\\ &= (\textbf{x}_i \cdot \textbf{x}_j)^2. \end{aligned} \]

On remarque qu’on n’a pas besoin de calculer les valeurs \(x^2, \sqrt{2}xy\) ou \(y^2\).

Transformation polynomiale

Pour le polynome multinomial, on a

\[\Phi(\textrm{x}) = \sum_{\textbf{J} \in \{0, 1, \dots, N\}} w_{\textrm{J}} \prod_{i = 1}^{k}x_{J_i}.\] Ce vecteur contient les données toutes les combinaisons polynomiales de dimension k. Par exemple,

\[x_1^k, x_2^k, \dots, x_p^k,\] \[x_1, x_1^2,\dots, x_1^{k-1}, x_1^{k},\] \[x_1^{k-1}x_2, x_1^{k-2}x_2^2, \dots, x_1 x_2^{k-1},\] \[x_1^{k-1}x_2, x_1^{k-1}x_3, \dots, x_1^{k-1}x_p\]

Transformation polynomiale

La transformation produit des données dans une dimension\((p + 1)^k\). Par contre, on peut montrer que

\[\Phi(\textrm{x})\cdot \Phi(\textrm{y}) = (1 + \textrm{x}\cdot \textrm{y})^k.\] Cette équation se calcule en \(O(N)\).

Transformation gaussienne

Soit la transformation

\[\Phi_k(\textrm{x}) = \frac{1}{\sqrt{k!}}e^{-\frac{||\textrm{x}||^2}{2}}\prod_{i = 1}^N\frac{x_{J_i}}{\sigma} .\]

On considère l’espace d’attributs de toutes les combinaisons de \(\Phi_k(\textrm{x}), k\in \mathbb{N}\).

Alors, on a

\[\Phi(\textrm{x})\cdot \Phi(\textrm{y}) = e^{-\frac{||\textrm{x} - \textrm{y}||^2}{2\sigma^2}}\]

On a seulement besoin de calculer une distance euclidienne, au lieu de calculer le produit scalaire entre deux vecteurs de dimension infini.

Fonction noyau

• Pour l’ACP avec noyau, on a seulement besoin du produit scalaire
• \(\Phi\) peut être une fonction non définie ou de dimension infinie, tant que son produit scalaire existe.
• Soit \[k(\textrm{x}, \textrm{y}) = \Phi(\textrm{x})\cdot \Phi(\textrm{y}).\] Alors, on peut écrire la matrice de covariance de \(\Phi\) comme

\[\frac{1}{N} \sum_{i = 1}^{N} \Phi(\textbf{x}_i)\cdot \Phi(\textbf{x}_i) = \frac{1}{N} \sum_{i = 1}^{N} k(\textrm{x}_i, \textrm{x}_i).\]

Normalisation des données

• La formule \[\frac{1}{N} \sum_{i = 1}^{N} \textrm{k}(\textrm{x}, \textrm{x})\] est valide si les données sont centrées, c-à-d que \[\sum_{i = 1}^{N} \Phi(\textrm{x}_i) = 0.\]

• Si \(\Phi(\textrm{x})\) est de dimension infinie, il est impossible de vérifier cette hypothèse.

Normalisation des données

La solution est proposée par (Schölkopf, Smola, and Müller 1997)

Soit \[K_{ij} = (k(\textbf{x}_i, \textbf{x}_j))_{ij} \textrm{ et } K,\]

la matrice des \(K_{ij}\). Alors, on peut centrer la matrice \(\tilde{K}\) selon

\[\tilde{K}_{ij} = K - 1_NK - K1_N + 1_NK1_N\]

où \((1_N)_{ij} := \frac{1}{N}\) et éviter de calculer les données \(\Phi(\textbf{x})\).

Rappel de l’ACP

Mathématiquement, les composantes principales sont obtenues selon une décomposition par valeurs et vecteurs propres de la matrice de covariances

\[ \frac{1}{N} \sum_{i = 1}^{N} \textbf{x}_i\textbf{x}_i^T.\] Correspond à la meilleure projection des données dans une dimension réduite.

ACP avec noyau

On applique une ACP sur les données projetées (Schölkopf, Smola, and Müller 1997). On décompose la matrice de covariances de la matrice des transformations non linéaires

\[ \frac{1}{N} \sum_{i = 1}^{N} \Phi(\textbf{x}_i)\Phi(\textbf{x}_i)^T = \frac{1}{N} \sum_{i = 1}^{N} \textrm{k}(\textrm{x}_i, \textrm{x}_i) .\]

Lien avec le SVM

Rappel : On veut maximiser \(M\) tel que \[y_i(\beta_0 + \beta_1 x_{i1} \dots + \beta_p x_{ip}) \geq M(1 - \varepsilon_i) ~ \forall ~ i = 1, \dots, n\] sous les contraintes \[ \begin{aligned} \sum_{j= 0}^p\beta_j^2 &= 1\\ \varepsilon_i &\geq 0 ~\forall~i\\ \sum_{i = 1}^n\varepsilon_i &\leq c \end{aligned} \]

Classifieur à vecteurs de support : formulation duale avec marges douces

Avec les multiplicateurs de Lagrange, la fonction à maximiser devient

\[-\frac{1}{2} \sum_{t = 1}^n\sum_{s = 1}^n \alpha_t\alpha_s r_tr_s\textbf{x}_t\textbf{x}_s^T + \sum_{t = 1}^n \alpha_t\] sous les contraintes

\[ \begin{aligned} \sum_{t= 1}^n\alpha_tr_t &= 0\\ 0\leq \alpha_i &\leq c ~\forall~i\\ \end{aligned} \]

Applications MNIST

On applique l’ACP avec noyau sur le jeu de données MNIST (LeCun et al. 1998).

Applications MNIST

Discussion

Avantages

• Découvrir les relations non linéaires entre les données
• Possiblement réduire davantage la dimension
• Noyau = truc utile lorsque seulement le produit scalaire est requis
• Succès dans détection de visages (K. I. Kim, Jung, and Kim 2002)

Discussion

Incovénients

• Ajuster les hyper-paramètres
• Non-supervisé : l’ajustement des hyper-paramètres peur être compliqué
• Perte de l’interprétabilité linéaire des premières composantes principales
• Ne permet pas de reconstruire les données